/*************************************************************************
 * File Name:    Edit_Distance.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-6 13:14:44
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Edit Distance
 | Given two words word1 and word2, find the minimum number of steps required
 | to convert word1 to word2. (each operation is counted as 1 step.)
 |
 | You have the following 3 operations permitted on a word:
 |
 | a) Insert a character
 | b) Delete a character
 | c) Replace a character
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2)
    {
        int m = word1.size();
        int n = word2.size();
        int dp[m + 1][n + 1];
        
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        
        for (int j = 1; j <= n; ++j) {
            for (int i = 1; i <= m; ++i) {
                dp[i][j] = dp[i - 1][j] + 1; // b)
                
                if (word1[i - 1] == word2[j - 1]) { // equal
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                } else {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1); // c)
                    dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1); // a)
                }
            }
        }
        return dp[m][n];
    }
};

int
main(int argc, char *argv[])
{
    Solution sol;

    string word1 = "a";
    string word2 = "ab";

    cout << sol.minDistance(word1, word2) << endl;

    return 0;
}
